package com.fw.structure.huffmancode;

import lombok.Data;
import lombok.ToString;

import java.io.*;
import java.util.*;

/**
 *赫夫曼编码 压缩，解压，以及对所有二进制的支持详细说明.
 */
public class HuffManCode {

    // 统计项，用来存储 赫夫曼 编码 左0 右1 这样的组合结构
    private static Map<Byte,String> huffManCodeMap = new HashMap<>();

    // 10101001101111 组合 赫夫曼 编码
    private static StringBuilder huffManCodeStr = new StringBuilder();

    public static void main(String[] args) throws UnsupportedEncodingException {

        /**
         * 赫夫曼编码 进行压缩的说明步骤
         */
        // String strContent = "i like like like java do you like a java";
        // 1. 得到一个字节数组 （对需要编码的数据进行字节化） 105, 32, 108, 105, 107, 101, 32...
        // byte[] strContentBytes = strContent.getBytes(); //40
        //System.out.println(strContentBytes.length);
       // System.out.println(Arrays.toString(strContentBytes));
        //2. 创建赫夫曼树形结构 用来得到编码➡️准备，因为需要取树的 路径
        // HuffManNode huffManNode =   createHuffManTree(strContentBytes);
        //3. 获取 赫夫曼 编码
        //createHuffManCode(huffManNode,"",huffManCodeStr);
        // Map<Byte, String> code = getCode(huffManNode);
        //4. code values 即是 对应的编码
       // byte[] zipByteCode = zip(strContentBytes,code); // 17
       // System.out.println(Arrays.toString(zipByteCode));
        // 至此 编码完善.

        /**
         * 赫夫曼解码 进行数据解压的说明步骤
         */
        //1. 先构建一个 将 一个 byte 的字节 转为 补码的过程
        //System.out.println( byteToString(true,(byte)-32));
        //2. 转化后 形成赫夫曼 编码
        // byte[] decodeBytes =   decode(huffManCodeMap,zipByteCode); //40 恢复
       // System.out.println(new String(decodeBytes).length());

        /**
         * 对文件的 解压缩操作
         * 写出后，无法打开，因为这是自定义的 编码方式，只能自己解开
         */
      //fileCompress("/Users/yanwei/Desktop/src.bmp","/Users/yanwei/Desktop/src1.bmp");
        fileDecompression("/Users/yanwei/Desktop/src1.bmp","/Users/yanwei/Desktop/src2.bmp");
    }

    /**
     * 对源文件进行赫夫曼解码 输出到目标文件
     * @param sourceFilePath 源文件
     * @param destFilePath   目标文件
     */
    private static void fileDecompression(String sourceFilePath,String destFilePath){
        try(ObjectInputStream fileInputStream = new ObjectInputStream(new FileInputStream(sourceFilePath)); FileOutputStream  fileOutputStream = new FileOutputStream(destFilePath)) {

            // 按照写出的顺序在读取
            // 1.读取的 编码
            byte[] codeBytes = (byte[]) fileInputStream.readObject();
            // 2.读取赫夫曼 编码表 用来复原
            Map<Byte,String> huffManCodeMap = (Map<Byte, String>) fileInputStream.readObject();
            byte[] decodeBytes = decode(huffManCodeMap,codeBytes);
            fileOutputStream.write(decodeBytes);
            fileOutputStream.flush();
        }catch (Exception e){
            e.printStackTrace();
        }
    }
    /**
     * 对源文件进行赫夫曼编码 输出到目标文件
     * @param sourceFilePath 源文件
     * @param destFilePath   目标文件
     */
    private static void fileCompress(String sourceFilePath,String destFilePath){
      //  FileInputStream fileInputStream = null;
        try(FileInputStream fileInputStream = new FileInputStream(sourceFilePath);  ObjectOutputStream  objectOutputStream = new ObjectOutputStream(new FileOutputStream(destFilePath))) {
            byte[] sourceBytes = new byte[fileInputStream.available()];
            fileInputStream.read(sourceBytes);
           // System.out.println(sourceBytes.length);
            byte[] bytes = huffManecode(sourceBytes);
            //System.out.println(bytes.length);
            // 使用 对象流写出，方便读取的时候管理
            objectOutputStream.writeObject(bytes);
            // 把 赫夫曼 编码表 写出，需要还原
            objectOutputStream.writeObject(huffManCodeMap);
            objectOutputStream.flush();
        }catch (Exception e){
        e.printStackTrace();
        }
    }


    /**
     * 赫夫曼  编码分装处理
     */
    private static byte[] huffManecode(byte[] bytes){
        //1. 生成 赫夫曼 树结构
        HuffManNode huffManTree = createHuffManTree(bytes);
        //2。 读取 赫夫曼 树结构的 路径节点数据 进一步过去 编码
        Map<Byte, String> code = getCode(huffManTree);
        // 得到编码后 进行二进制处理操作
        byte[] zip = zip(bytes, code);
        return zip;
    }

    /**
     *
     * @param huffManCodeMap 对应的 赫夫曼 存储结构
     * @param zipByteCode 解码出来的数据
     * @return
     */
    private static byte[] decode(Map<Byte, String> huffManCodeMap, byte[] zipByteCode) {
        // 存储  赫夫曼编码
        StringBuilder codes = new StringBuilder();
        for (int i = 0; i < zipByteCode.length; i++) {
            // 最后一步了，不用 按位与
            boolean flag =  (i == zipByteCode.length -1);
            codes.append(byteToString(!flag,zipByteCode[i]));
        }
        // 把所有 赫夫曼编码 取出后 开始匹配。
        // 匹配 huffManCodeMap 将对应的源数据匹配出来
        // 将其 huffManCodeMap 数据反转 因为 需要根据 code 进行获取
        Map<String,Byte> revMaps = new HashMap<>();
        huffManCodeMap.forEach((key,val) -> revMaps.put(val,key));

        // 开始匹配得到 byte 数据
        List<Byte> byteDataLists = new ArrayList<>();

        // 进行匹配，此时 codes 是一堆编码，需要不断地扫描这个编码 进而匹配数据
        for (int i = 0; i < codes.length();) {
            // while 循环控制器
            boolean flag = true;
            // 计数器
            int count = 1;
            // 存储介质
            Byte b = null;
            while (flag){
                // 进行扫描
                // 逻辑非常简单，从 i - i + count 的方式截取.
                // 0-1，匹配到之后 i的值发生改变
                String key = codes.substring(i,i + count);
                b =   revMaps.get(key);
                if (b == null){
                    count ++;
                }else{
                    flag = false;
                }
            }
            byteDataLists.add(b);
            i+=count;
        }

        byte[] bytes = new byte[byteDataLists.size()];

        for (int i = 0; i < bytes.length; i++) {
            bytes[i] = byteDataLists.get(i);
        }
        return bytes;
    }


    /**
     *
     * @param flag  true = 需要 按位与  false = 不需要
     * @param b 需要补码的字节数据
     * @return
     */
    private static String byteToString(boolean flag,byte b){
      int temp = b;
      if (flag){
         temp |= 256;
      }
        String binaryString = Integer.toBinaryString(temp);
      if (flag){
          return binaryString.substring(binaryString.length() - 8);
      }else{
          return binaryString;
      }

    }




    /**
     *  用来处理 编码的容积问题，转为二进制
     * @param strContentBytes
     * @param code
     * @return
     */
    private static byte[] zip(byte[] strContentBytes, Map<Byte, String> code) {
        //1.利用 huffmanCodes 将  bytes 转成  赫夫曼编码对应的字符串
        // 此处出现了一个测试事故，StringBuilder 使用的是 成员变量，导致 上方加密的时候，数据连带了。
        StringBuilder stringBuilder = new StringBuilder();
        for (int i = 0; i < strContentBytes.length; i++) {
            stringBuilder.append(code.get(strContentBytes[i]));
        }
        //System.out.println(huffManCodeStr.toString());
        // 开始处理
        // 要得到 byte 的容积
        int len;
        if(stringBuilder.length() % 8 == 0) {
            len = stringBuilder.length() / 8;
        } else {
            len = stringBuilder.length() / 8 + 1;
        }
        byte[] zipByteCode = new byte[len];
        int index = 0;//索引值
        for (int i = 0; i < stringBuilder.length(); i += 8) { // 一个字节 8 bit 每次拿 8 bit 数据即可.
            String strByte;
            if(i+8 > stringBuilder.length()) {// 如果是最后一位，i+8 就会有问题。
                strByte = stringBuilder.substring(i);
            }else{
                strByte = stringBuilder.substring(i, i + 8);
            }
            // 将二进制输出为十进制
            zipByteCode[index] = (byte)Integer.parseInt(strByte, 2);
            index++;
        }
        return zipByteCode;

    }

    /**
     * 简易化操作
     * @param huffManNode
     * @return
     */
    private static Map<Byte,String> getCode(HuffManNode huffManNode){
        if (huffManNode != null){
            createHuffManCode(huffManNode.leftNode,"0",huffManCodeStr);
            createHuffManCode(huffManNode.rightNode,"1",huffManCodeStr);

        }
        return huffManCodeMap;
    }

    /**
     * 获取 赫夫曼 编码  相当 解析这颗树，将左0右1 的树路径进行组合为 标准化编码
     * @param huffManNode
     * @param code // 左0右1
     */
    private static void createHuffManCode(HuffManNode huffManNode,String code,StringBuilder huffManCodeStr) {
        StringBuilder stringBuilder2 = new StringBuilder(huffManCodeStr);
   //将 code 加入到 stringBuilder2
        stringBuilder2.append(code);
       // 是否是非叶子节点
        if ( huffManNode != null && huffManNode.getData() == null){
            // 是非叶子节点
            if (huffManNode.leftNode != null) {
                createHuffManCode(huffManNode.leftNode,"0",stringBuilder2);
            }
            if (huffManNode.rightNode != null) {
                createHuffManCode(huffManNode.rightNode,"1",stringBuilder2);
            }
        }else{
            huffManCodeMap.put(huffManNode.getData(),stringBuilder2.toString());
        }

    }


    /**
     * 创建对应的  赫夫曼 节点结构
     * @param strContentBytes
     * @return
     */
    private static HuffManNode createHuffManTree(byte[] strContentBytes) {
        // 统计出 strContentBytes 出现的次数
        Map<Byte,Integer> strContentNums = new HashMap<>();
        for (byte strContentByte : strContentBytes) {
                strContentNums.merge(strContentByte,1,(oldVal,newVal) -> oldVal + newVal);
        }
       // 将 strContentNums 构建为 节点先
        List<HuffManNode> huffManNodeList = new ArrayList<>();
        strContentNums.forEach((key,val)->{
            huffManNodeList.add(new HuffManNode(key,val));
        });
        // 将 huffManNodeList 做成标准化  赫夫曼 结构
        while (huffManNodeList.size() >1){
            Collections.sort(huffManNodeList);
            // 开始操作
            HuffManNode leftNode = huffManNodeList.get(0);
            HuffManNode rightNode = huffManNodeList.get(1);
            HuffManNode parentNode = new HuffManNode();
            parentNode.setData(null);
            parentNode.setNum(leftNode.getNum() + rightNode.getNum());
            parentNode.leftNode = leftNode;
            parentNode.rightNode = rightNode;
            huffManNodeList.remove(leftNode);
            huffManNodeList.remove(rightNode);
            huffManNodeList.add(parentNode);
        }

        return huffManNodeList.get(0);
    }
}

/**
 * 赫夫曼 节点结构
 */
@ToString
@Data
class HuffManNode implements Comparable<HuffManNode>{
    // 数据值 如果是非叶子节点 该值为空
    private Byte data;
    // data 出现的次数
    private Integer num;
    @ToString.Exclude
    public HuffManNode leftNode;
    @ToString.Exclude
    public HuffManNode rightNode;
    public HuffManNode() {
    }

    public HuffManNode(Byte data, Integer num) {
        this.data = data;
        this.num = num;
    }

    @Override
    public int compareTo(HuffManNode o) {
        return this.num - o.num;
    }
}